//
// Created by francklinson on 2021/6/16.
//

//给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    int trap1(vector<int> &height) {
        /**
         * 每一块柱形上面都可以有水，水量由左右最高柱形及当前柱形的高度决定
         * 找到每一块柱形左边和右边最高的柱形
         */
        int n = (int) height.size();
        vector<int> left(n, 0), right(n, 0);
        // 左边
        for (int i = 0; i < n - 1; ++i) {
            left[i + 1] = max(left[i], height[i]);
        }
        // 右边
        for (int i = n - 1; i > 0; --i) {
            right[i - 1] = max(right[i], height[i]);
        }
        // 算每块柱形水量
        int ans = 0;
        for (int i = 1; i < n - 1; ++i) {
            int water = min(left[i], right[i]);
            ans += water > height[i] ? water - height[i] : 0;
        }
        return ans;
    }

    int trap2(vector<int> &height) {
        /**
         * 单调递减栈 遇到比栈顶更大的方块，则可以形成一段蓄水区
         */
        int ans = 0;
        stack<int> stk;
        int n = (int) height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top(); // top元素
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top(); // left元素  height[left] > height[top]
                int currWidth = i - left - 1; // 蓄水区宽度
                int currHeight = min(height[left], height[i]) - height[top]; // 蓄水区高度
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }

    int trap3(vector<int> &height) {
        /**
         * 双指针
         */
        int ans = 0;
        int left = 0, right = (int) height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]); // 更新左侧最高
            rightMax = max(rightMax, height[right]); // 更新右侧最高
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};


int main() {
    vector<int> height{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    Solution sol;
    cout << sol.trap3(height) << endl;
    return 0;
}